/*
 * @Descripttion: 
 * @version: 
 * @Author: lily
 * @Date: 2021-05-25 17:14:42
 * @LastEditors: lily
 * @LastEditTime: 2021-05-25 18:39:42
 */
/*
 * @lc app=leetcode.cn id=289 lang=javascript
 *
 * [289] 生命游戏
 */

// @lc code=start
/**
 * @param {number[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */

//  思路：
//  模拟，根据每一个细胞周围情况进行赋值，需要注意的是二维数组的深拷贝
//  由于只有0/1两个转换，可以扩展两个复合状态，如-1表示从 死->活，2表示从 活->死
//  从而降低空间复杂度到O(1)
//  https://leetcode-cn.com/problems/game-of-life/solution/sheng-ming-you-xi-by-leetcode-solution/

//  复杂度：O(mn) O(mn)

var gameOfLife = function (board) {
    const rl = board.length, cl = board[0].length
    // 二维数组深拷贝
    let copy = []
    for (const row of board) {
        copy.push(row.slice())
    }

    for (let i = 0; i < rl; i++) {
        for (let j = 0; j < cl; j++) {
            // 活细胞
            let xs = i - 1 < 0 ? 0 : i - 1, xe = i + 1 >= rl ? rl - 1 : i + 1
            let ys = j - 1 < 0 ? 0 : j - 1, ye = j + 1 >= cl ? cl - 1 : j + 1
            let num = 0
            // 找周边有多少个活细胞
            for (let x = xs; x <= xe; x++) {
                for (let y = ys; y <= ye; y++) {
                    if (x === i && y === j) {
                        continue
                    }
                    if (copy[x][y]) {
                        num++
                    }
                }
            }

            // 根据细胞数进行赋值
            if (copy[i][j]) {  // 当前为活细胞
                if (num < 2 || num > 3) {
                    board[i][j] = 0
                }
            } else { // 当前为死细胞
                if (num === 3) {
                    board[i][j] = 1
                }
            }
        }
    }
};
// @lc code=end

let board = [[1, 1], [1, 0]]
gameOfLife(board)
console.log(board);